Ý tưởng Đường_đi_Euler

Thành phố Konigsberg (Đức) có 2 vùng bị ngăn cách bởi một dòng sông và có 2 đảo ở giữa sông. Có 7 chiếc cầu nối những vùng này với nhau.

Hình ảnh 7 chiếc cầu nối 4 vùng trong thành phố Konigsberg (Đức)

Bài toán: Người dân trong vùng thách đố nhau là thử tìm cách xuất phát từ một vùng đi dạo qua mỗi chiếc cầu đúng một lần và trở về nơi xuất phát.

Năm 1736, nhà toán học Euler (1707 - 1783) đã mô hình bài toán này bằng một đồ thị vô hướng với mỗi đỉnh ứng với một vùng, mỗi cạnh ứng với một chiếc cầu.

Đồ thị vô hướng được mô hình hóa từ bài toán 7 chiếc cầu